#include "msrch.h"



struct kword** OutArray;

int* FailArray;

int HighState;

int* MatchArray;    //第一层匹配

union GotoTable* GotoArray;

int MaxState;

void AddStateTrans(int oldState, int matchChar, int newState)
{
	if(MatchArray[oldState]==EMPTY_SLOT)
	{
		MatchArray[oldState] = matchChar;
		GotoArray[oldState].GotoState = newState;
	}
	if(MatchArray[oldState]==MULTI_WAY)
		GotoArray[oldState].BranchTable[matchChar] = newState;

	else
	{
		int* tmp  = (int*)calloc(sizeof(int), MAXCHAR);
		int i = 0;
		for(i=0;i<MAXCHAR;i++)
			tmp[i] = FAIL_STATE;
		
		tmp[matchChar] = newState;

		MatchArray[oldState] = MULTI_WAY;
		GotoArray[oldState].BranchTable = tmp;
	}

}



void Enter(unsigned char* word)
{
	int state = 0, k;
	char* save = (char*)word;
	
	struct kword* ktmp = null;

	for(;*word!='\0';word++)
	{
		if(MatchArray[state] == *word)
			state = GotoArray[state].GotoState;
		else if(MatchArray[state]==MULTI_WAY)
		{
			if((k=GotoArray[state].BranchTable[*word])==FAIL_STATE)
				break;
			else
				state = k;
		}
		else
			break;
	}

	for(;*word!='\0';word++)
	{
		HighState += 1;
		if(HighState > MaxState)
		{
			fputs("INTERNAL ERROR: too many states:\n", stderr);
			exit(1);
		}

		AddStateTrans(state, *word, HighState);
		state = HighState;
	}

	ktmp = (struct kword*)calloc(sizeof(struct kword), 1);
	ktmp->word = (unsigned char*)save;
	ktmp->next = OutArray[state];
	OutArray[state] = ktmp;
}

void ComputeFail(void)
{
	int *queue, qbeg, r, s;
	int i;

	queue = (int*)calloc(sizeof(int), MaxState);

	qbeg = 0;

	queue[0] = 0;

	for(i=0;i<MAXCHAR;i++)
	{
		if((s=GotoArray[0].BranchTable[i])!=0)
		{
			FailArray[s] = 0;
			QueueAdd(queue, qbeg, s);
		}

		while(queue[qbeg]!=0)
		{
			r = queue[qbeg];
			qbeg = r;

			if(MatchArray[r]==EMPTY_SLOT)
				continue;
			else if(MatchArray[r]==MULTI_WAY)
			{
				for(i=0;i<MAXCHAR;i++)
				{
					if((s=GotoArray[r].BranchTable[i])!=FAIL_STATE)
					{
						QueueAdd(queue, qbeg, s);
						FindFail(FailArray[r], s, i);
					}
				}

			}
			else
			{
				QueueAdd(queue, qbeg, GotoArray[r].GotoState);
				FindFail(FailArray[r], GotoArray[r].GotoState, MatchArray[r]);
			}
		}
	}
	free(queue);
}

void FindFail(int s1, int s2, int a)
{
	int on_fail;
	struct kword *ktemp, kdummy, *out_copy, *kscan;

	for ( ; ; s1 = FailArray[s1] )
	{
		if ( MatchArray[s1] == a )
		{
			if (( on_fail = GotoArray[s1].GotoState ) != FAIL_STATE )
				break;
		}
		else if ( MatchArray[s1] != EMPTY_SLOT )
			if (( on_fail = GotoArray[s1].BranchTable[a] )!= FAIL_STATE )
				break;
	}

	FailArray[s2] = on_fail;
	/* merge output lists */
	/* first, make a copy of OutArray[on_fail] */
	if ( OutArray[on_fail] == NULL )
		out_copy = NULL;
	else
	{
		kscan = OutArray[on_fail];
		out_copy = (struct kword*)malloc ( sizeof ( struct kword ));
		out_copy->word = kscan->word;
		out_copy->next = NULL;
		for ( kscan = kscan->next;kscan != NULL;kscan = kscan->next )
		{
			ktemp = (struct kword*)malloc ( sizeof ( struct kword ));
			ktemp->word = kscan->word;
			ktemp->next = out_copy->next;
			out_copy->next = ktemp;
		}
	}
	/* now merge them */
	if (( kdummy.next = OutArray[s2] ) != NULL )
	{
		ktemp = &kdummy;
	    for ( ; ktemp->next->next != NULL; ktemp = ktemp->next );
		ktemp->next->next = out_copy;
	}
	else
		OutArray[s2] = out_copy;
}

void QueueAdd(int *queue, int qbeg, int newEle)
{
	int q;
	q = queue[qbeg];
	if(q==0)
		queue[qbeg] = newEle;
	else
	{
		for(;queue[q]!=0;q=queue[q]);

		queue[q] = newEle;
	}
	queue[newEle] = 0;
}

void MsrchInit(struct kword* klist)
{
	int i = 0;
	struct kword* ktmp = null;
	MaxState = 1;
	for(ktmp=klist;ktmp!=null;ktmp=ktmp->next)
		MaxState += strlen(ktmp->word);
	
	MatchArray = (int *)calloc(sizeof(int), MaxState);
	GotoArray = (union GotoTable*)calloc(sizeof(union GotoTable), MaxState);
	OutArray = (struct kword **)calloc(sizeof(struct kword *), MaxState);
	FailArray = (int *)calloc(sizeof(int), MaxState);
	
	for(i=0;i<MaxState;i++)
	{
		MatchArray[i] = EMPTY_SLOT;
		OutArray[i] = null;
	}

	HighState = 0;

	AddStateTrans(0, 'a', FAIL_STATE);

	AddStateTrans(0, 'b', FAIL_STATE);

	for(ktmp=klist;ktmp!=null;ktmp=ktmp->next)
		Enter(ktmp->word);

	for(i=0;i<MAXCHAR;i++)
		if(GotoArray[0].BranchTable[i]==FAIL_STATE)
			GotoArray[0].BranchTable[i]=0;
	
	ComputeFail();
}


void MsrchGo(int (*MsrchData)(), void (*MsrchSignal)(char*))
{
	int state, c, g, m;
	struct kword *kscan;

	state = 0;
    while (( c = MsrchData() ) != EOF )
    {
        /* what is goto ( state, c ) ? */
        for ( ;; )
        {
            /*-------------------------------------------------
             *  We cheat slightly in the interest of
             *  speed/simplicity. The machine will spend most
             *  of its time in state==0, and this state is
             *  always a MULTI_WAY table. Since this is a
             *  simple test, we make it first and try to save
             *  the calculation of an array index
             *-----------------------------------------------*/

            if ( state == 0 ||
                 ( m = MatchArray[state] ) == MULTI_WAY )
                g = GotoArray[state].BranchTable[c];
            else
            if ( m == c )
                g = GotoArray[state].GotoState;
			else
				g = FAIL_STATE;

            if ( g != FAIL_STATE )
				break;

            state = FailArray[state];
		}
		state = g;

		/* anything to output? */
        if (( kscan = OutArray[state] ) != NULL )
            for ( ; kscan != NULL; kscan = kscan->next )
                MsrchSignal ( (char*)kscan->word );
	}
}
void MsrchEnd()
{
	int i;
	struct kword *kscan;

    for ( i = 0; i < MaxState; i++ )
          if ( MatchArray[i] == MULTI_WAY )
               free ( GotoArray[i].BranchTable );

    free ( MatchArray );
    free ( GotoArray );
    free ( FailArray );

    for ( i = 0; i < MaxState; i++ )
        if ( OutArray[i] != NULL )
             for ( kscan = OutArray[i];
                   kscan!=NULL;
                   kscan = kscan->next )
                 free ( kscan );
    free ( OutArray );
}

